class Codec:
    def serialize(self, root):
        """Encodes a tree to a single string.
https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/
297. 二叉树的序列化与反序列化

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

提示: 输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

        :type root: TreeNode
        :rtype: str
        """
        self.mark(root, 1)
        res = self.to_nfs(root) + "\n" + self.to_mfs(root)
        return res

    def deserialize(self, data):
        """Decodes your encoded data to tree.

        :type data: str
        :rtype: TreeNode
        """
        all = data.split('\n')
        nfs = all[0]
        mfs = all[1]
        return self.restore(nfs, mfs)

    def restore(self, nfs, mfs):
        #print(mfs)
        if not nfs or not mfs:
            return None

        node = nfs[:nfs.index('\t')]
        root = TreeNode(int(node[node.index('#')+1:]))
        if '\t' + node + '\t' in mfs:
            idx = mfs.index('\t' + node + '\t') + 1
        elif mfs.startswith(node + '\t'):
            idx = 0

        left = mfs[0:idx]
        right = mfs[idx+len(node)+1:]
        root.left = self.restore(nfs[len(node)+1:len(node)+1+len(left)], left)
        root.right = self.restore(nfs[len(node)+1+len(left):], right)
        return root

    def mark(self, root, id):
        if not root:
            return id
        root.id = id
        left = self.mark(root.left, id + 1)
        right = self.mark(root.right, left + 1)
        return right + 1

    def to_nfs(self, root):
        if not root:
            return ""
        result = str(root.id) + "#" + str(root.val) + "\t"
        result = result + self.to_nfs(root.left)
        result = result + self.to_nfs(root.right)
        return result
    def to_mfs(self, root):
        if not root:
            return ""
        result = ""
        result = result + self.to_mfs(root.left)
        result = result + str(root.id) + "#" + str(root.val) + "\t"
        result = result + self.to_mfs(root.right)
        return result
